package org.example;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 图结构的DFS/BFS遍历
public class Graph1 {
    // 邻接表和邻接矩阵实现图结构
    // 邻接表：邻接表很直观，把每个节点x的邻居都存到一个列表里，然后把x和这个列表映射起来，这样就可以通过一个节点x找到它的所有相邻节点
    // 邻接矩阵：则是一个二维布尔数组，权且称为matrix，如果节点x和y是相连的，
    //  那么就把matrix[x][y]设为true。如果想找节点x的邻居，去扫一圈matrix[x][...]就行了。

    // 如果用代码的形式来表现，邻接表和邻接矩阵大概长这样：
    /*
        // 邻接表
        // graph[x] 存储 x 的所有邻居节点
        List<Integer>[] graph;

        // 邻接矩阵
        // matrix[x][y] 记录 x 是否有一条指向 y 的边
        boolean[][] matrix;
    */
    // 邻接表和邻接矩阵的使用场景
    /*
        // 邻接表
        // graph[x] 存储 x 的所有邻居节点以及对应的权重
        // 具体实现不一定非得这样，可以参考后面的通用实现
        class Edge {
            int to;
            int weight;
        }
        List<Edge>[] graph;

        // 邻接矩阵
        // matrix[x][y] 记录 x 指向 y 的边的权重，0 表示不相邻
        int[][] matrix;
    */
    static class Edge {
        int to;
        int weight;
    }

    // 这其实是有向加权图的接口，但基于这个接口可以实现所有不同种类的无向/有向/无权/加权图。下面给出具体代码。
    interface Graph {
        // 添加一条边（带权重）
        void addEdge(int from, int to, int weight);

        // 删除一条边
        void removeEdge(int from, int to);

        // 判断两个节点是否相邻
        boolean hasEdge(int from, int to);

        // 返回一条边的权重
        int weight(int from, int to);

        // 返回某个节点的所有令居节点和对应权重
        List<Edge> neighbors(int v);

        // 返回节点总数
        int size();
    }

    // 有向加权图（邻接表）
    // 加权有向图的通用实现（邻接表）
    static class WeightedDigraph {
        // 存储相邻节点及边的权重
        public static class Edge {
            int to;
            int weight;

            public Edge(int to, int weight) {
                this.to = to;
                this.weight = weight;
            }
        }

        // 邻接表，graph[v]存储节点v的所有邻居节点及对应权重
        // 数组里面套了List集合
        private List<Edge>[] graph;

        public WeightedDigraph(int n) {
            // 我们这里简单起见，建图时要传入节点总数，这其实可以优化
            // 比如把graph设置为Map<Integer, List<Edge>>，就可以动态添加新节点了
            graph = new ArrayList[n];
            for (int i = 0; i < n; i++) {
                graph[i] = new ArrayList<>();
            }
        }

        // 增，添加一条带权重的有向边，复杂度O(1)
        public void addEdge(int from, int to, int weight) {
            graph[from].add(new Edge(to, weight));
        }

        // 删除一条有向边，复杂度O(V)
        public void removeEdge(int from, int to) {
            for (int i = 0; i < graph[from].size(); i++) {
                if (graph[from].get(i).to == to) {
                    graph[from].remove(i);
                    break;
                }
            }
        }

        // 查询，判断两个节点是否相邻，复杂度O(V)
        public boolean hasEdge(int from, int to) {
            for (Edge e : graph[from]) {
                if (e.to == to) {
                    return true;
                }
            }
            return false;
        }

        // 查询， 返回一条边的权重，复杂度O(V)
        public int weight(int from, int to) {
            for (Edge e : graph[from]) {
                if (e.to == to) {
                    return e.weight;
                }
            }
            throw new IllegalArgumentException("No such edge");
        }

        // 上面的hasEdge、removeEdge、weight方法遍历List的行为是可以优化的
        // 比如用Map<Integer, Map<Integer, Integer>>存储邻接表
        // 这样就可以避免遍历List,复杂度就能降到O(1)

        // 查询，返回某个节点的所有的邻居节点，复杂度O(1)
        public List<Edge> neighbors(int v) {
            return graph[v];
        }

        public static void main(String[] args) {
            WeightedDigraph graph = new WeightedDigraph(3);
            graph.addEdge(0, 1, 1);
            graph.addEdge(1, 2, 2);
            graph.addEdge(2, 0, 3);
            graph.addEdge(2, 1, 4);

            System.out.println(graph.hasEdge(0, 1)); // true
            System.out.println(graph.hasEdge(1, 0)); // false

            graph.neighbors(2).forEach(edge -> {
                System.out.println(2 + "->" + edge.to + ", weight: " + edge.weight);
            });
            // 2 -> 0, wight: 3
            // 2 -> 1, wight: 4

            graph.removeEdge(0, 1);
            System.out.println(graph.hasEdge(0, 1)); // false

        }
    }

    // 有向加权图（邻接矩阵实现）
    static class WeightedDigraph1 {
        // 存储相邻节点及边的权重
        static class Edge {
            int to;
            int weight;

            public Edge(int to, int weight) {
                this.to = to;
                this.weight = weight;
            }
        }

        // 邻接矩阵，matrix[from][to]存储从节点from到节点to的边的权重
        // 0 表示没有连接
        private int[][] matrix;

        public WeightedDigraph1(int n) {
            matrix = new int[n][n];
        }

        // 增加一条带权重的有向边，复杂度O(1)
        public void addEdge(int from, int to, int weight) {
            matrix[from][to] = weight;
        }

        // 删除一条带权重的有向边，复杂度O(1)
        public void removeEdge(int from, int to) {
            matrix[from][to] = 0;
        }

        // 查询，判断两个节点是否相邻，复杂度O(1)
        public boolean hasEdge(int from, int to) {
            return matrix[from][to] != 0;
        }

        // 查询，返回一条边的权重，复杂度O(1)
        public int weight(int from, int to) {
            return matrix[from][to];
        }

        // 查询，返回某个节点的所有邻居节点，复杂度O(V)
        public List<Edge> neighbors(int v) {
            List<Edge> res = new ArrayList<>();
            for (int i = 0; i < matrix[v].length; i++) {
                if (matrix[v][i] > 0) {
                    res.add(new Edge(i, matrix[v][i]));
                }
            }
            return res;
        }

        public static void main(String[] args) {
            WeightedDigraph1 graph = new WeightedDigraph1(3);
            graph.addEdge(0, 1, 1);
            graph.addEdge(1, 2, 2);
            graph.addEdge(2, 0, 3);
            graph.addEdge(2, 1, 4);
            System.out.println(graph.hasEdge(0, 1)); // true
            System.out.println(graph.hasEdge(1, 0)); // false

            graph.neighbors(2).forEach(edge -> {
                System.out.println(2 + " -> " + edge.to + ", wight: " + edge.weight);
            });
            // 2 -> 0, wight: 3
            // 2 -> 1, wight: 4

            graph.removeEdge(0, 1);
            System.out.println(graph.hasEdge(0, 1)); // false
        }
    }

    // 有向无权图（邻接表/邻接矩阵实现）
    // 直接复用上面的 WeightedDigraph 类就行，把 addEdge 方法的权重参数默认设置为 1 就行了。比较简单，我就不写代码了。

    // 无向加权图（邻接表/邻接矩阵实现）
    // 无向加权图就等同于双向的有向加权图，所以直接复用上面用邻接表/领接矩阵实现的 WeightedDigraph 类就行了，只是在增加边的时候，要同时添加两条边：

    // 无向加权图的通用实现
    static class WeightedUndigraph {
        private WeightedDigraph graph;

        public WeightedUndigraph(int n) {
            graph = new WeightedDigraph(n);
        }

        // 增加一条带权重的无向边
        public void addEdge(int from, int to, int weight) {
            graph.addEdge(from, to, weight);
            graph.addEdge(to, from, weight);
        }

        // 删除一条无向边
        public void removeEdge(int from, int to) {
            graph.removeEdge(from, to);
            graph.removeEdge(to, from);
        }

        // 查询，判断两个节点是否相邻
        public boolean hasEdge(int from, int to) {
            return graph.hasEdge(from, to);
        }

        // 查询，返回一条边的权重
        public int weight(int from, int to) {
            return graph.weight(from, to);
        }

        // 查询，返回某个节点的所有邻居节点
        public List<WeightedDigraph.Edge> neighbors(int v) {
            return graph.neighbors(v);
        }

        public static void main(String[] args) {
            WeightedUndigraph graph = new WeightedUndigraph(3);
            graph.addEdge(0, 1, 1);
            graph.addEdge(1, 2, 2);
            graph.addEdge(2, 0, 3);
            graph.addEdge(2, 1, 4);

            System.out.println(graph.hasEdge(0, 1)); // true
            System.out.println(graph.hasEdge(1, 0)); // true

            graph.neighbors(2).forEach(edge -> {
                System.out.println(2 + " <-> " + edge.to + ", wight: " + edge.weight);
            });
            // 2 <-> 0, wight: 3
            // 2 <-> 1, wight: 4

            graph.removeEdge(0, 1);
            System.out.println(graph.hasEdge(0, 1)); // false
            System.out.println(graph.hasEdge(1, 0)); // false
        }
    }

    // 无向无权图（邻接表/邻接矩阵实现）
    // 直接复用上面的 WeightedUndigraph 类就行，把 addEdge 方法的权重参数默认设置为 1 就行了。比较简单，我就不写代码了。


    // 图结构的DFS/BFS遍历
    // 图的遍历就是 多叉树遍历 的延伸，主要遍历方式还是深度优先搜索（DFS）和广度优先搜索（BFS）。
    // 唯一的区别是，树结构中不存在环，而图结构中可能存在环，所以我们需要标记遍历过的节点，避免遍历函数在环中死循环。
    // 遍历图的「节点」和「路径」略有不同，遍历「节点」时，需要 visited 数组在前序位置标记节点；遍历图的所有「路径」时，需要 onPath 数组在前序位置标记节点，在后序位置撤销标记。

    // 【深度优先搜索（DFS）】
    // >>>>>>遍历所有节点（visited 数组）<<<<<<
    // 对比多叉树的遍历框架看图的遍历框架吧：
    static class DFS {
        // 多叉树节点
        static class Node {
            int val;
            List<Node> children;
        }

        // 多叉树的遍历框架
        void traverse(Node root) {
            // base case
            if (root == null) {
                return;
            }
            // 前序位置
            System.out.println("visit " + root.val);
            for (Node child : root.children) {
                traverse(child);
            }
            // 后序位置
        }

        static class Vertex {
            int id;
            Vertex[] neighbors;
        }

        // 图的遍历框架
        // 需要一个 visited 数组记录被遍历过的节点
        // 避免走回头路陷入死循环

        void traverse(Vertex s, boolean[] visited) {
            // base case
            if (s == null) {
                return;
            }
            if (visited[s.id]) {
                // 防止死循环
                return;
            }

            // 前序位置
            visited[s.id] = true;
            System.out.println("visit " + s.id);
            for (Vertex neighbor : s.neighbors) {
                traverse(neighbor, visited);
            }
            // 后序位置
        }
        // 可以看到，图的遍历比多叉树的遍历多了一个 visited 数组，用来记录被遍历过的节点，避免遇到环时陷入死循环。
        /*
        为什么成环会导致死循环
        举个最简单的成环场景，有一条 1 -> 2 的边，同时有一条 2 -> 1 的边，节点 1, 2 就形成了一个环：
        1 <=> 2
        如果我们不标记遍历过的节点，那么从 1 开始遍历，会走到 2，再走到 1，再走到 2，再走到 1，如此 1->2->1->2->... 无限递归循环下去。
        如果有了 visited 数组，第一次遍历到 1 时，会标记 1 为已访问，出现 1->2->1 这种情况时，发现 1 已经被访问过，就会直接返回，
        从而终止递归，避免了死循环。
        */

        // 遍历图的所有节点
        void traverse(Graph graph, int s, boolean[] visited) {
            // base case
            if (s < 0 || s >= graph.size()) {
                return;
            }
            if (visited[s]) {
                // 防止死循环
                return;
            }
            // 前序遍历
            visited[s] = true;
            System.out.println("visit " + s);
            for (Edge e : graph.neighbors(s)) {
                traverse(graph, e.to, visited);
            }
            // 后序位置
        }
        // 由于visited数组的剪枝作用，这个遍历函数会遍历一次图中的所有节点，并尝试遍历一次所有边，所以算法的时间复杂度是O(E+V)，其中E是边的总数，V是节点总数
    }

    // 遍历所有路径（onPath数组）
    // 对于树结构，遍历所有【路径】和遍历所有【节点】是没有什么区别的。而对于图结构，遍历所有【路径】和遍历所有【节点】稍有不同。
    // 因为对于树结构来说，只能由父节点指向子节点，所以从根节点root出发，到任意一个节点targetNode的路径都是唯一的。
    // 换句话说，我遍历一遍树结构的所有节点之后，必然可以找到root到targetNode的唯一路径。

    // 多叉树的遍历框架，寻找从根节点到目标节点的路径
    static class MultiTreeOnPathTraversal {
        static class Node {
            int val;
            List<Node> children;
        }

        LinkedList<Node> path = new LinkedList<>();

        void traverse(Node root, Node targetNode) {
            // base case
            if (root == null) {
                return;
            }
            // 前序位置
            path.addLast(root);
            if (root.val == targetNode.val) {
                System.out.println("find path: " + path);
            }
            for (Node child : root.children) {
                traverse(child, targetNode);
            }
            // 后序位置
            path.removeLast();
        }
    }
    // 而对于图结构来说，由起点 src 到目标节点 dest 的路径可能不止一条。我们需要一个 onPath 数组，在进入节点时（前序位置）标记为正在访问，
    // 退出节点时（后序位置）撤销标记，这样才能遍历图中的所有路径，从而找到 src 到 dest 的所有路径：

    // 下面的算法代码可以遍历图的所有路径，寻找从 src 到 dest 的所有路径
    static class GraphOnPath {
        // onPath 和path记录当前递归路径上的节点
        boolean[] onPath;
        List<List<Integer>> res  = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public List<List<Integer>> graphOnPath(Graph graph) {
            onPath = new boolean[graph.size()];
            traverse(graph, 0, graph.size() - 1);
            return res;
        }


        void traverse(Graph graph, int src, int dest) {
            // base case
            if (src < 0 || src >= graph.size()) {
                res.add(new LinkedList<>(path));
                path.removeLast();
                return;
            }
            if (onPath[src]) {
                // 防止死循环（成环）
                return;
            }
            // 前序位置
            onPath[src] = true;
            path.add(src);
            if (src == dest) {
                System.out.println("find path: " + path);
            }
            for (Edge e : graph.neighbors(src)) {
                traverse(graph, e.to, dest);
            }
            // 后序位置
            path.remove(path.size() - 1);
            onPath[src] = false;
        }
    }

    // 如果使用前文遍历节点的算法，只在前序位置标记 visited 为 true，那么遍历完 1->2->4 和 1->2->3->4 之后，
    // 所有节点都已经被标记为已访问了，算法就会停止，visited 数组完成了自己的职责。

    // 但是显然我们还没有遍历完所有路径，1->3->2->4 和 1->3->4 被漏掉了。
    // 如果用 onPath 数组在离开节点时（后序位置）撤销标记，就可以找到 1 到 4 的所有路径。

    // 由于这里使用的 onPath 数组会在后序位置撤销标记，所以这个函数可能重复遍历图中的节点和边，复杂度一般较高（阶乘或指数级），
    // 具体的时间复杂应该是所有路径的长度之和，取决于图的结构特点。

    // 【同时使用visited和onPath数组】
    // 按照上面的分析，visited数组和onPath分别用于遍历所有节点和遍历所有路径。那么它们两个是否可能会同时出现呢？答案是可能得。
    // 遍历所有路径的算法复杂度较高，大部分情况下我们可能并不需要穷举完所有路径，而是仅需要找到某一条符合条件的路径。
    // 这种场景下，我们可能会借助visited数组进行剪枝，提前排除一些不符合条件的路径，从而降低复杂度。

    // 【完全不用visited和onPath数组】
    // 是否有既不用visited数组，也不用onPath数组的场景呢？其实也是有的
    // 前面介绍了，visited 和 onPath 主要的作用就是处理成环的情况，避免死循环。
    // 那如果题目告诉你输入的图结构不包含环，那么你就不需要考虑成环的情况了。

    // 797. 所有可能的路径
    // 给你一个有 n 个节点的 有向无环图（DAG），请你找出所有从节点 0 到节点 n-1 的路径并输出（不要求按特定顺序）
    //
    // graph[i] 是一个从节点 i 可以访问的所有节点的列表（即从节点 i 到节点 graph[i][j]存在一条有向边）。
    // 输入：graph = [[1,2],[3],[3],[]]
    // 解释：[[1,2],[3],[3],[]]
    //         0    1   2   3
    // 表示0指向1，也指向2；1指向3；2指向3；3无指向
    // 输出：[[0,1,3],[0,2,3]]
    // 解释：有两条路径 0 -> 1 -> 3 和 0 -> 2 -> 3
    static class AllPathsSourceTarget {
        // 记录所有路径
        List<List<Integer>> res = new LinkedList<>();
        LinkedList<Integer> path = new LinkedList<>();

        public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
            traverse(graph, 0);
            return res;
        }

        // 图的遍历框架
        void traverse(int[][] graph, int s) {
            // 添加节点s到路径
            path.addLast(s);
            int n = graph.length;
            if (s == n - 1) {
                // 到达终点
                res.add(new LinkedList<>(path));
                path.removeLast();
                return;
            }
            // 递归每个相邻节点
            for (int v : graph[s]) {
                traverse(graph, v);
            }
            // 从路径移出节点s
            path.removeLast();
        }
    }

    // 【广度优先搜索（BFS）】
    // 图结构的广度优先搜索其实就是 多叉树的层序遍历，无非就是加了一个 visited 数组来避免重复遍历节点。
    // 理论上 BFS 遍历也需要区分遍历所有「节点」和遍历所有「路径」，但是实际上 BFS 算法一般只用来寻找那条最短路径，不会用来求所有路径。
    // 当然 BFS 算法肯定也可以求所有路径，但是我们一般会选择用 DFS 算法求所有路径
    // 那么如果只求最短路径的话，只需要遍历「节点」就可以了，因为按照 BFS 算法一层一层向四周扩散的逻辑，第一次遇到目标节点，必然就是最短路径。

    // 图结构的 BFS 算法框架也有三种不同的写法，下面我会对比着多叉树的层序遍历写一下图结构的三种 BFS 算法框架。

    // 【写法一：第一种写法是不记录遍历步数】
    // 多叉树的层序遍历
    static class LevelOrderTraverse1 {

        static class Node {
            int val;
            List<Node> children;
        }

        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            while (!queue.isEmpty()) {
                Node cur = queue.poll();
                // 访问cur节点
                System.out.println(cur.val);
                // 把cur的所有子节点加入队列
                for (Node child : cur.children) {
                    queue.offer(child);
                }
            }
        }
    }

    // 图结构的BFS遍历，从节点s开始进行BFS
    static class BFS1 {
        void bfs(Graph graph, int s) {
            boolean[] visited = new boolean[graph.size()];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(s);
            visited[s] = true;

            while (!queue.isEmpty()) {
                int cur = queue.poll();
                System.out.println("visit " + cur);
                for (Edge e : graph.neighbors(cur)) {
                    if (!visited[e.to]) {
                        queue.offer(e.to);
                        visited[e.to] = true;
                    }
                }
            }
        }
    }

    // 【写法二：第二种能够记录遍历步数的写法】
    static class LevelOrderTraverse2 {

        static class Node {
            int val;
            List<Node> children;
        }

        // 多叉树的层序遍历
        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<Node> queue = new LinkedList<>();
            queue.offer(root);
            // 记录当前遍历的层数（根节点视为第1层）
            int depth = 1;

            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    Node cur = queue.poll();
                    // 访问cur节点，同时知道它所在的层数
                    System.out.println("depth = " + depth + ", val = " + cur.val);
                    for (Node child : cur.children) {
                        queue.offer(child);
                    }
                }
                depth++;
            }
        }
    }

    static class BFS2 {
        // 从 s 开始 BFS 遍历图的所有节点，且记录遍历的步数
        void bfs(Graph graph, int s) {
            boolean[] visited = new boolean[graph.size()];
            Queue<Integer> queue = new LinkedList<>();
            queue.offer(s);
            visited[s] = true;
            // 记录从s开始走到当前节点的步数
            int step = 0;
            while (!queue.isEmpty()) {
                int sz = queue.size();
                for (int i = 0; i < sz; i++) {
                    int cur = queue.poll();
                    System.out.println("visit " + cur + " at step " + step);
                    for (Edge e : graph.neighbors(cur)) {
                        if (!visited[e.to]) {
                            queue.offer(e.to);
                            visited[e.to] = true;
                        }
                    }
                }
                step++;
            }
        }
        // 这个 step 变量记录了从起点 s 开始的遍历步数，对于无权图来说，相当于每条边的权重都是 1，这个变量就可以辅助我们判断最短路径。
    }

    // 【写法三：第三种能够适配不同权重边的写法】
    // 多叉树的层序遍历
    // 每个节点自行维护State类，记录深度等信息
    static class LevelOrderTraverse3 {
        static class Node {
            int val;
            List<Node> children;
        }

        static class State {
            Node node;
            int depth;

            public State(Node node, int depth) {
                this.node = node;
                this.depth = depth;
            }
        }

        void levelOrderTraverse(Node root) {
            if (root == null) {
                return;
            }
            Queue<State> queue = new LinkedList<>();
            // 记录当前遍历到的层数（根节点视为第1层）
            queue.offer(new State(root, 1));

            while (!queue.isEmpty()) {
                State state = queue.poll();
                Node cur = state.node;
                int depth = state.depth;
                // 访问cur节点，同时知道它所在的层数
                System.out.println("depth = " + depth + ", val = " + cur.val);
                for (Node child : cur.children) {
                    queue.offer(new State(child, depth + 1));
                }
            }
        }
    }

    // 图结构的BFS遍历，从节点s开始进行BFS，且记录路径的权重和
    // 每个节点自行维护State类，记录从s走来的权重和
    static class BFS3 {
        static class State {
            // 当前节点ID
            int node;
            // 从起点s到当前节点的权重和
            int weight;

            public State(int node, int weight) {
                this.node = node;
                this.weight = weight;
            }
        }

        void bfs(Graph graph, int s) {
            boolean[] visited = new boolean[graph.size()];
            Queue<State> queue = new LinkedList<>();

            queue.offer(new State(s, 0));
            visited[s] = true;

            while (!queue.isEmpty()) {
                State state = queue.poll();
                int cur = state.node;
                int weight = state.weight;
                System.out.println("visit " + cur + " with path weight " + weight);
                for (Edge e : graph.neighbors(cur)) {
                    if (!visited[e.to]) {
                        queue.offer(new State(e.to, weight + e.weight));
                        visited[e.to] = true;
                    }
                }
            }
            // 对于加权图，由于每条边的权重不同，遍历的步数不再能代表最短路径的长度，所以需要每个节点用自定义 State 类维护自己的路径权重和
        }
    }


}
